package com.algorithm;

public class BagCode {

    public static void main(String[] args) {

        int[] prices = {60, 100, 120};
        int[] kg = {1, 2, 4};
        System.out.println(bag(5, kg, prices));
    }

public static int bag(int size, int[] kg, int[] prices) {
    int[][] pk = new int[kg.length + 1][size + 1];
    //遍历每次加的物品
    for (int i = 1; i <= kg.length; i++) {
        //判断随着背包容量的增大，能获取的最大价值
        for (int k = 1; k <= size; k++) {
            if (k >= kg[i - 1]) {
                //装这个物品能获取大最大价值，就是在当前背包重量下装这个物品还剩余空间能装但最大价值，去上一层找这个最大价值
                int inPrice = prices[i - 1] + pk[i - 1][k - kg[i - 1]];
                int notInPrice = pk[i - 1][k];
                pk[i][k] = Math.max(inPrice, notInPrice);
            } else {
                pk[i][k] = pk[i - 1][k];
            }
        }
    }
    return pk[kg.length][size];
}


}
